package ttt;

import java.util.HashMap;
import java.util.Map;
import java.util.Random;
import java.util.Stack;

class TicTacToe {
	private static final int HUMAN = 0;
	private static final int COMPUTER = 1;
	public static final int EMPTY = 2;

	public static final int HUMAN_WIN = 0;
	public static final int DRAW = 1;
	public static final int UNCLEAR = 2;
	public static final int COMPUTER_WIN = 3;

	private int[][] board = new int[3][3];
	private Stack<Integer> option;
	private Random random = new Random();
	private int side = random.nextInt(2);
	private int position = UNCLEAR;
	private char computerChar, humanChar;
	private Map<int[][], Integer> positions = new HashMap<int[][], Integer>();

	// Constructor
	public TicTacToe() {
		clearBoard();
		initSide();
		option = new Stack();
	}

	private void initSide() {
		if (this.side == COMPUTER) {
			computerChar = 'X';
			humanChar = 'O';
		} else {
			computerChar = 'O';
			humanChar = 'X';
		}
	}

	public void setComputerPlays() {
		this.side = COMPUTER;
		initSide();
	}

	public void setHumanPlays() {
		this.side = HUMAN;
		initSide();
	}

	public boolean computerPlays() {
		return side == COMPUTER;
	}

	public int chooseMove() {
		Best best = chooseMove(COMPUTER, 0, HUMAN_WIN, COMPUTER_WIN);
		return best.row * 3 + best.column;
	}

	// Find optimal move
	private Best chooseMove(int side, int amountCheckedBestMoves, int human,
			int computer) {
		int opp;
		Best reply;
		int simpleEval;
		int bestRow = 0;
		int bestColumn = 0;
		int value;
		if ((simpleEval = positionValue()) != UNCLEAR)
			return new Best(simpleEval);
		int[][] tmpBoard = board.clone();
		if (amountCheckedBestMoves >= 3 && amountCheckedBestMoves <= 5) {
			Integer pos = positions.get(tmpBoard);
			if (pos != null) {
				return new Best(pos);
			}
		}
		if (side == COMPUTER) {
			opp = HUMAN;
			value = HUMAN_WIN;
		} else {
			opp = COMPUTER;
			value = COMPUTER_WIN;
		}
		for (int i = 0; i < (board.length * board[0].length); i++) {
			int row = i / board.length;
			int column = i % board[0].length;

			if (squareIsEmpty(row, column)) {
				place(row, column, side);
				reply = chooseMove(opp, amountCheckedBestMoves + 1, human,
						computer);
				place(row, column, EMPTY);
				if (side == HUMAN && reply.val < value || side == COMPUTER
						&& reply.val > value) {
					
					if (side == HUMAN) {
						computer = reply.val;
						value = computer;
					} else {
						human = reply.val;
						value = human;
					}
					bestRow = row;
					bestColumn = column;
					if (human >= computer)
						break;
				}
			}
		}
		if (amountCheckedBestMoves <= 5) {
			positions.put(tmpBoard, value);
		}
		return new Best(value, bestRow, bestColumn);
	}

	private boolean oneMoveAway() {
		if ((board[0][0] == side) && (board[0][1] == side)
				&& (board[0][2] == side)) {
			return true;
		}
		if ((board[1][0] == side) && (board[1][1] == side)
				&& (board[1][2] == side)) {
			return true;
		}
		if ((board[2][0] == side) && (board[2][1] == side)
				&& (board[2][1] == side)) {
			return true;
		}
		if ((board[0][0] == side) && (board[1][0] == side)
				&& (board[2][0] == side)) {
			return true;
		}
		if ((board[0][1] == side) && (board[1][1] == side)
				&& (board[2][1] == side)) {
			return true;
		}
		if ((board[0][2] == side) && (board[1][2] == side)
				&& (board[2][2] == side)) {
			return true;
		}
		if ((board[0][0] == side) && (board[1][1] == side)
				&& (board[2][2] == side)) {
			return true;
		}
		if ((board[0][2] == side) && (board[1][1] == side)
				&& (board[2][0] == side)) {
			return true;
		}
		return false;
	}

	private TicTacToe copy() {
		TicTacToe copy = new TicTacToe();

		if (this.computerPlays()) {
			copy.setComputerPlays();
		} else {
			copy.setHumanPlays();
		}

		for (int row = 0; row < board.length; row++) {
			for (int column = 0; column < board[0].length; column++) {
				copy.place(row, column, board[row][column]);
			}
		}

		return copy;
	}

	// check if move ok
	public boolean moveOk(int move) {
		return (move >= 0 && move <= 8 && board[move / 3][move % 3] == EMPTY);
	}

	// play move
	public void playMove(int move) {
		board[move / 3][move % 3] = this.side;
		if (side == COMPUTER)
			this.side = HUMAN;
		else
			this.side = COMPUTER;
	}

	// Simple supporting routines
	private void clearBoard() {
		for (int i = 0; i < board.length; i++) {
			for (int j = 0; j < 3; j++) {
				;
				board[i][j] = EMPTY;
			}
		}
	}

	private boolean boardIsFull() {
		for (int i = 0; i < board.length; i++) {
			for (int y : board[i]) {
				if (board[i][y] == 2) {
					return false;
				}
			}
		}
		return true;
	}

	// Returns whether 'side' has won in this position
	/**
	 * Winning combinations are: 0-1-2 3-4-5 6-7-8 0-3-6 1-4-7 2-5-8 0-4-8 2-4-6
	 */
	private boolean isAWin(int side) {
		if ((board[0][0] == side) && (board[0][1] == side)
				&& (board[0][2] == side)) {
			return true;
		}
		if ((board[1][0] == side) && (board[1][1] == side)
				&& (board[1][2] == side)) {
			return true;
		}
		if ((board[2][0] == side) && (board[2][1] == side)
				&& (board[2][1] == side)) {
			return true;
		}
		if ((board[0][0] == side) && (board[1][0] == side)
				&& (board[2][0] == side)) {
			return true;
		}
		if ((board[0][1] == side) && (board[1][1] == side)
				&& (board[2][1] == side)) {
			return true;
		}
		if ((board[0][2] == side) && (board[1][2] == side)
				&& (board[2][2] == side)) {
			return true;
		}
		if ((board[0][0] == side) && (board[1][1] == side)
				&& (board[2][2] == side)) {
			return true;
		}
		if ((board[0][2] == side) && (board[1][1] == side)
				&& (board[2][0] == side)) {
			return true;
		}
		return false;
	}

	// Play a move, possibly clearing a square
	private void place(int row, int column, int piece) {
		board[row][column] = piece;
	}

	private boolean squareIsEmpty(int row, int column) {
		return board[row][column] == EMPTY;
	}

	// Compute static value of current position (win, draw, etc.)
	private int positionValue() {
		if (isAWin(COMPUTER)) {
			return COMPUTER_WIN;
		} else if (isAWin(HUMAN)) {
			return HUMAN_WIN;
		} else if (boardIsFull()) {
			return DRAW;
		} else {
			return UNCLEAR;
		}
	}

	public String toString() {
		StringBuilder buffer = new StringBuilder();
		String indentation = " ";
		String horizontalLine = "___________";
		String verticalLine = "|";
		String newLine = "\n";

		buffer.append("Human : ").append(humanChar);
		buffer.append(newLine);
		buffer.append("Computer : ").append(computerChar);
		buffer.append(newLine);

		for (int row = 0; row < board.length; row++) {
			for (int column = 0; column < board[0].length; column++) {
				int currentLocation = board[row][column];
				buffer.append(indentation);
				if (currentLocation == COMPUTER) {
					buffer.append(computerChar);
				} else if (currentLocation == HUMAN) {
					buffer.append(humanChar);
				} else {
					buffer.append(indentation);
				}
				buffer.append(indentation);
				if (column != board[0].length - 1) {
					buffer.append(verticalLine);
				}
			}
			if (row != board.length - 1) {
				buffer.append(newLine);
				buffer.append(horizontalLine);
				buffer.append(newLine);
			}
		}

		return buffer.toString();
	}

	public boolean gameOver() {
		this.position = positionValue();
		return this.position != UNCLEAR;
	}

	public String winner() {
		if (this.position == COMPUTER_WIN)
			return "computer";
		else if (this.position == HUMAN_WIN)
			return "human";
		else
			return "nobody";
	}

	private class Best {
		int row;
		int column;
		int val;

		public Best(int v) {
			this(v, 0, 0);
		}

		public Best(int v, int r, int c) {
			val = v;
			row = r;
			column = c;
		}
	}

}